class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int left = nums.size() - 2;
        for (; left >= 0; left--)
            if (nums[left] < nums[left + 1])
                break;

         if (left < 0)
        {
            reverse(nums.begin(), nums.end());
            return;
        }

        int right = nums.size() - 1;
        for (; right >= left; right--)
            if (nums[right] > nums[left]) 
                break;
        
         swap(nums[left], nums[right]);

        int _left = left + 1, _right = nums.size() - 1;
        while (_left <= _right)
        {
            swap(nums[_left], nums[_right]);
            _left++;
            _right--;
        }
    }
};